Computation of paths within a computer network, e.g., for tunnels through the network, is generally performed in either an unconstrained or a constrained manner. For unconstrained path computation, such as according to a Shortest Path First (SPF) algorithm, a path computation device (e.g., router) may determine a shortest path (e.g., based on a path metric, such as cost) between a source node (“source”) and one or more destination nodes (“destinations”) using any available link in the computer network. When performing constrained path computation, such as a Constrained SPF (CSPF), on the other hand, the device may determine a shortest path between the source and destination using only links in the network that meet one or more configured constraints. Notably, constraints may be configured for any number of attributes, such as a minimum bandwidth value of a link, a maximum latency, maximum cost, etc. For example, tunnels such as Multi-Protocol Label Switching (MPLS) Traffic Engineering (TE) Label Switched Paths (LSPs) may be computed using CSPF, as will be understood by those skilled in the art.
One problem associated with CSPF path computation is that the configured constraints are “hard” constraints, such that any link that does not meet the constraints (e.g., that has less bandwidth than the minimum bandwidth, higher latency than the maximum latency, etc.) is removed from a set of links used for the shortest path computation. In particular, this may result in a high path cost in order to meet the constraints (e.g., minimum bandwidth) where only high cost links remain that meet the constraints. Often, this high cost path may be used even though a substantially lower cost path may have been found by “relaxing” the constraints, i.e., configuring less stringent constraints. That is, conventional CSPF uses hard/static constraints, and does not allow for a “tradeoff” to be considered between constraints (e.g., relaxing one attribute constraint that results in another attribute having a more favorable value).
For instance, assume a system administrator requests computation for a 100 megabits per second (Mbps) tunnel from a source to a destination (i.e., a minimum bandwidth constraint of 100 Mbps). By performing a CSPF computation, it may be determined that a shortest path has a cost of “200”. Conversely, had the bandwidth constraint been reduced (relaxed) to 90 Mbps, the cost may have also been reduced, e.g., significantly, such as to a shortest path having a cost of “100”. In other words, a tradeoff exists where meeting one attribute/constraint, e.g., bandwidth, may result in other unsatisfactory attribute values, such as high cost, high delay, high jitter, etc., while meeting a lesser (relaxed) constraint (e.g., 10% lower bandwidth) may result in more favorable attribute values (e.g., 50% lower cost). There is generally no known efficient manner to determine whether relaxation of certain attribute constraints might produce more favorable values for other attributes and, thus, this determination is generally not performed. Although the administrator may manually attempt different constraint values, such an attempt is not efficient to determine a substantially optimal tradeoff between attributes.
In addition, a worst case result of using hard constraints for CSPF is where no satisfactory paths are found from the source to the destination(s) (e.g., no paths meet the 100 Mbps constraint above). In that worst case, the path computation fails and, if desired, a new set of configured (hard) constraints that has been relaxed may be manually configured by the system administrator for a new CSPF computation, e.g., until a satisfactory path is found. However, such configuration is inefficient and cumbersome, and is difficult to guarantee an optimal path solution (e.g., where constraints become more relaxed than need be), particularly where constraints are manually relaxed.